package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 最大二叉树
 * @date 2025/4/22 13:24
 */
public class ConstructMaximumBinaryTree_654 {

    public static void main(String[] args) {
        ConstructMaximumBinaryTree_654 constructMaximumBinaryTree654 = new ConstructMaximumBinaryTree_654();

        int[] nums = new int[]{3, 2, 1, 6, 0, 5};
        TreeNode node = constructMaximumBinaryTree654.constructMaximumBinaryTree(nums);
        System.out.println(node);
    }

    /**
     * 个解：dfs-递归-先序
     * <p>
     * 这里是左闭右闭，而dmsxl是左闭右开
     * <p>
     * 思路：
     * 1.题目已知 nums 无重复元素。
     * 2.构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
     * 3.移动索引使用逻辑数组。
     * 4.移动索引同从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树。
     * <p>
     * 复杂度：
     * T(n) = O(n^2)； 是数组 nums 的长度。在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i (0≤i<n)层需要遍历 n−i 个元素以找出最大值，总时间复杂度为 O(n^2)。
     * S(n) = O(n)；最坏情况下需要使用的栈空间。
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    public TreeNode dfs(int[] nums, int startIndex, int endIndex) {
        if (endIndex < startIndex) return null;

        // 1.找最大元素下标
        int maxIndex = getMaxIndex(nums, startIndex, endIndex);
        TreeNode node = new TreeNode(nums[maxIndex]);
        // 叶子节点，直接返回
        if (startIndex == endIndex) return node;

        // 2.分割数组
        // 逻辑新数组起止下标（左闭右闭）
        int leftStart = startIndex;
        int leftEnd = maxIndex - 1;
        int rightStart = maxIndex + 1;
        int rightEnd = endIndex;

        // 3.递归处理左右
        TreeNode left = dfs(nums, leftStart, leftEnd);
        TreeNode right = dfs(nums, rightStart, rightEnd);
        node.left = left;
        node.right = right;

        return node;
    }

    public int getMaxIndex(int[] nums, int start, int end) {
        int max = nums[start], maxIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

}
